Many radar, sonar, telecommunication and other systems require the computation of Fourier Transforms. As a result, many computational devices and methods exist. For instance, one common structure, which is based on the radix 2 Cooley-Tukey algorithm, involves recursively performing two complex multiplications with reordering between stages. This structure includes two channels, commonly referred to as the I- and Q-channels, to accommodate the real and imaginary parts of complex inputs.
When such a structure is used to implement real input FFT's, one channel is typically zeroed out, thereby wasting half of the hardware. It has been shown that this waste may be partially avoided by feeding a second real sequence to the previously unused channel simultaneously with the first. However, this technique results in a scrambled output. In other words, the FFT outputs corresponding to the two input sequences are intermixed. This necessitates extra hardware to unscramble the output and offsets most or all of the increased efficiency realized by simultaneously processing two data sequences.